A search engine is a computer program that helps a user to locate information. Using a search engine, a user can enter one or more search query terms and obtain a list of resources that contain or are associated with subject matter that matches those search query terms. While search engines may be applied in a variety of contexts, search engines are especially useful for locating resources that are accessible through the Internet. Resources that may be located through a search engine include, for example, files whose content is composed in a page description language such as Hypertext Markup Language (HTML). Such files are typically called pages. One can use a search engine to generate a list of Universal Resource Locators (URLs) and/or HTML links to files, or pages, that are likely to be of interest.
Some search engines order a list of files before presenting the list to a user. To aid the user in the search, a search engine may rank the files according to relevance. Relevance is a measure of how closely the subject matter of the file matches query terms. When the list is sorted by rank, a file with a relatively higher rank may be placed closer to the head of the list than a file with a relatively lower rank. The user, when presented with the sorted list, sees the most highly ranked files first.
To find the most relevant files, search engines typically try to select, from among a plurality of files, files that include many or all of the words that a user entered into a search request. If the user has misspelled a word in the search request, then the search engine may fail to select files in which the correctly spelled word occurs.
If a search engine determines that a term in a search query may be misspelled, the search engine may present the user with an alternative search query that includes a different spelling for the term. In many cases, the alternative search query will provide better results than the original search query. However, sometimes the search engine suggests an alternative search query that would not produce suitable search results.
At best, presenting the user with an unsuitable spelling suggestion in an alternative search query is merely an annoyance to the user. Even if the user ignores the alternative search query, the user's time is taken to analyze the alternative search query to decide whether to submit it. However, it may be difficult for the user to tell whether the alternative search query will lead to an acceptable search result without trying the search query. If the user does submit the inappropriate alternative search query, the user's time is wasted waiting for and examining the alternative search results.
In other cases, a user may enter a search request containing a correctly spelled word that does not mean the thing for which the user desires to search. Because there are no incorrectly spelled words in the search request, the search engine may fail to even attempt to determine an alternative spelling. For example, a user who wants to find files that include information about “Silicon Valley” may request a search for “Silicone Valley.” Because “Silicone” is a correctly spelled word, a search engine may not detect any error. Under such circumstances, the user is likely to obtain a list of results that have little to do with what the user was actually looking for.
Thus, there is a need for improved ways of suggesting alternative formulations to search queries.
The approaches described in this section are approaches that could be pursued, but not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated, it should not be assumed that any of the approaches described in this section qualify as prior art merely by virtue of their inclusion in this section.